#include <iostream>

// 哈夫曼树节点定义
struct HuffmanNode
{
    HuffmanNode(int w) : weight(w), left(nullptr), right(nullptr) {}
    int weight;         // 权重
    HuffmanNode *left;  // 左孩子
    HuffmanNode *right; // 右孩子
};

// 选出两个权重最低的索引
void selectTwoMinNodes(HuffmanNode *nodes[], int size, int &min1, int &min2)
{
    min1 = -1;
    min2 = -1;

    for (int i = 0; i < size; ++i)
    {
        if (nodes[i] != nullptr)
        {
            if (min1 == -1 || nodes[i]->weight < nodes[min1]->weight)
            {
                min2 = min1;
                min1 = i;
            }
            else if (min2 == -1 || nodes[i]->weight < nodes[min2]->weight)
            {
                min2 = i;
            }
        }
    }
}

// 构建哈夫曼树
HuffmanNode *buildHuffmanTree(int *weights, int size)
{
    HuffmanNode *nodes[100]; // 假设最多100个节点
    int n = size;

    // 初始化节点数组
    for (int i = 0; i < n; ++i)
    {
        nodes[i] = new HuffmanNode(weights[i]);
    }

    for (int i = 0; i < n - 1; ++i)
    {
        int min1, min2;
        selectTwoMinNodes(nodes, n, min1, min2);

        // 创建新节点，并合并两个最小权重的节点
        HuffmanNode *newNode = new HuffmanNode(nodes[min1]->weight + nodes[min2]->weight);
        newNode->left = nodes[min1];
        newNode->right = nodes[min2];

        // 标记已经合并的节点
        nodes[min1] = newNode;
        nodes[min2] = nullptr;
    }

    // 返回根节点
    for (int i = 0; i < n; ++i)
    {
        if (nodes[i] != nullptr)
        {
            return nodes[i];
        }
    }

    return nullptr;
}

void PrevPrint(HuffmanNode *root)
{
    if (root == nullptr)
        return;
    std::cout << root->weight << " ";
    PrevPrint(root->left);
    PrevPrint(root->right);
}

void MidPrint(HuffmanNode *root)
{
    if (root == nullptr)
        return;
    MidPrint(root->left);
    std::cout << root->weight << " ";
    MidPrint(root->right);
}

int main()
{
    int weights[] = {5, 9, 12, 13, 16, 45};
    int size = sizeof(weights) / sizeof(weights[0]);

    HuffmanNode *root = buildHuffmanTree(weights, size);
    PrevPrint(root);
    std::cout << std::endl;
    MidPrint(root);
    std::cout << std::endl;

    return 0;
}